package com.zzy.algorithm.sort;

import java.util.Arrays;

public class Test {

    public static void main(String[] args) {

    }


    private int[] mergeSort(int[] nums){
        if(nums.length < 2){
            return nums;
        }
        int middle = nums.length / 2;
        int[] left = Arrays.copyOfRange(nums,0,middle);
        int[] right = Arrays.copyOfRange(nums,middle,nums.length);
        return combine(mergeSort(left),mergeSort(right));
    }

    private int[] combine(int[] left,int[] right){
        int[] result = new int[left.length + right.length];
        int p1 = 0;
        int p2 = 0;
        for(int i = 0 ; i < result.length ; i++){
            if(p1 > left.length - 1){
                result[i] = right[p2++];
            } else if(p2 > right.length - 1){
                result[i] = left[p1++];
            } else if(left[p1] > right[p2]){
                result[i] = right[p2++];
            } else {
                result[i] = left[p1++];
            }
        }
        return result;
    }


}
